package com.aqie.medium.sort;

/**
 * 215 数组中第k个最大元素
 * https://geekeye.cc/post/alg/selecting/quickselect_bfprt/
 */
public class FindKthLargest2 {
    /**
     * 7ms
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        return nums[select(nums, 0, nums.length - 1, k)];
    }

    /**
     * 返回数组 arr[left, right] 的第 k 小数的下标
     * @param arr 待处理的数组
     * @param left 待处理的数列在数组中的起始索引
     * @param right 待处理的数列在数组中的终止索引
     * @param k 第k小
     * @return 第k小的数在数组中的索引
     */
    public int select(int[] arr, int left, int right, int k) {
        int pivotIndex, partitionIndex, num;
        for (;;) {
            if (left == right) return left;
            // 得到中位数的中位数下标（即主元下标）
            pivotIndex = getPivotIndex(arr, left, right);
            // 进行划分，返回划分边界，即枢轴点的位置
            partitionIndex = partition(arr, left, right, pivotIndex);
            // 由于枢轴点已经排定，如果其位置与待选择的k位置一样，即返回，否则继续递归查找
            num = partitionIndex - left + 1;

            if (num == k) return partitionIndex;
            else if (num > k)  // 往左边继续找
                right = partitionIndex - 1;
            else  { // 往右边继续找
                k -= num;
                left = partitionIndex + 1;
            }
        }
    }


    /**
     * 中位数的中位数算法
     * 数组 arr[left, right] 每五个元素作为一组，并计算每组的中位数，\
     * 最后返回这些中位数的中位数下标（即主元下标）。
     *
     * 末尾返回语句最后一个参数多加一个 1 的作用其实就是向上取整的意思，
     * 这样可以始终保持 k 大于 0。
     *
     * @param arr 待处理的数组
     * @param left 待处理的数列在数组中的起始索引
     * @param right 待处理的数列在数组中的终止索引
     * @return 中位数的中位数下标
     */
    private int getPivotIndex(int[] arr, int left, int right) {
        if (right - left < 5)
            return insertionSort(arr, left, right);

        int subRight = left - 1;

        // 每五个作为一组，求出中位数，并把这些中位数全部依次移动到数组左边
        for (int i = left; i + 4 <= right; i += 5) {
            int index = insertionSort(arr, i, i + 4);
            swap(arr, ++subRight, index);
        }

        // 利用 select 得到这些中位数的中位数下标（即主元下标）
        return select(arr, left, subRight, ((subRight - left + 1) >> 1) + 1);
    }

    /**
     * 利用主元下标 pivotIndex 进行对数组 arr[left, right] 划分，并返回
     * 划分后的分界线下标。
     *
     * 类似快速排序的逻辑，都是将数组的元素与中轴点进行比较，但是并没有进行交换操作，
     * 只是分界后确定中轴点在数组中排定的位置
     */
    private int partition(int[] arr, int left, int right, int pivotIndex) {
        swap(arr, pivotIndex, right); // 把主元放置于末尾
        int partitionIndex = left; // 跟踪划分的分界线
        for (int i = left; i < right; i++) {
            if (arr[i] > arr[right]) {
                swap(arr, partitionIndex++, i); // 比主元大的都放在左侧
            }
        }
        swap(arr, partitionIndex, right); // 最后把主元换回来
        return partitionIndex;
    }

    /**
     * 对数组 array[left, right] 进行插入排序
     * @param arr 待处理的数组
     * @param left 待处理的数列在数组中的起始索引
     * @param right 待处理的数列在数组中的终止索引
     * @return [left, right] 的中位数。
     */
    private int insertionSort(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            for (int j = i; j > left && arr[j-1] < arr[j]; j--) {
                swap(arr, j-1, j);
            }
        }
        return ((right - left) >> 1) + left;
    }

    /**
     * 交换数据中两个特定位置的数据
     * @param arr 待处理的数组
     * @param i 位置i
     * @param j 位置j
     */
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
